package window;
import java.util.*;

import org.junit.Test;
public class Ex438 {
    class SolutionX {
        public List<Integer> findAnagrams(String s, String p) {
            List<Integer> res = new ArrayList<>();
            Deque<Character> deque = new LinkedList<>();
            Map<Character, Integer> map = new HashMap<>();
            int len1 = s.length(), len2 = p.length(), count = 0;
            char c;
            for (int i = 0; i < len2; i++) {
                map.put((c = p.charAt(i)), map.getOrDefault(c, 0) + 1);
                count++;
            }
            Map<Character, Integer> copy = new HashMap<>();
            copy.putAll(map);
            int hi = 0, lo = 0, cn;
            while (hi < len1) {
                while (count > 0 && hi < len1) {
                    if (map.containsKey((c = s.charAt(hi))) && (cn = map.get(c)) > 0) {
                        count--;
                        map.put(c, cn - 1);
                    } else if (!map.containsKey(c) || map.get(c) == 0) {
                        lo = hi; //重新开始计数
                        count = len2;
                        // map.clear();
                        map.putAll(copy);
                    }
                    hi++;
                }
                //将低位不属于模式串的部分去掉
                while (!map.containsKey((c = s.charAt(lo))) && hi - lo >= len2) {
                    lo++;
                }
                res.add(lo);

                //lo进一位，开始进行新一轮
                map.put(c, map.get(c) + 1);
                lo++;
                count++;
            }
            return res;
        }
    }
    class Solution {
        public List<Integer> findAnagrams(String s, String p) {
            int[] fre = new int[26];


//          表示窗口内相差的字符的数量
            int dif = 0;
            
            // fre 统计频数
            for (char c :
                    p.toCharArray()) {
                fre[c - 'a']++;
                dif++;
            }
            
            int left=0,right=0;
            int length = s.length();
            char[] array = s.toCharArray();
            
            List<Integer> result = new ArrayList<>();
            
            
            while (right < length) {
                char rightChar = array[right];
                
                
                //是p中的字符  
                if (fre[rightChar-'a'] > 0) {
                    fre[rightChar-'a']--;
                    //差距减少
                    dif--;
                    right++;

                    //差距减少为0时 说明窗口内为所求
                    if (dif == 0) {
                        result.add(left);
                    }


                }else{
                    //俩种情况 ： 第一种 rightChar 是p以外的字符串如"c" "abc" "ab" 此时 left 和 right 都应该指向 c后面的位置   
                    //          第二种 rightChar是p内的字符串但是是额外的一个char如第二个"b" 例 "abb" "ab" 此时right不变 
                    //left应该指向第一个b后面的位置
                    
                    //对于第一种情况 left 和 right 都应该定位到 c  所以要恢复fre数组 同时恢复差距
                    //对于第二种情况 此时fre[array[right]-'a']=0 让left移动到第一个b后面的位置 这样就融入了新的b（第二个b）
                    
                    while (fre[array[right]-'a']<=0 && left<right) {
                        fre[array[left]-'a']++;
                        left++;
                        dif++;
                    }

                    if (left == right ) {
                        
                        
                        //这个if用来检测right所处字符是否是p外的字符
                        
                        
                        //用来处理第二种情况 
                        if (fre[array[left] - 'a'] > 0) {
                            //说明是p里的字符 跳过
                            continue;
                        }else{
                        //用来处理第一种情况 移动到这个字符后面的位置
                            left++;
                            right++;
                        }

                    }
                }
            }

            return result;
        }
    }

    /* 
        java缺少像py那样直接比对字典的能力，因此只通过map记录所需元素需要map的o(len(p))的比对时间
        利用额外遍历count记录窗口还差多少元素可以变成p
        在窗口滑动时时根据各种情况维护count，一旦为0，返回窗口左边缘

        另外，对于题设已经给出全为小写字母，可以采取有限数组作为map，此map额外空间为O(1)
    */
    class Solution1 {
        public List<Integer> findAnagrams(String s, String p) {
        int len = s.length();
        if (p == null)  return new ArrayList<>();

        int[] map = new int[26]; //默认每一项为0
        int count = 0;
        for (char c: p.toCharArray()) {
            map[c - 'a']++;
            count++; //count == len(p)
        }
        char[] chs = s.toCharArray();
        int lo = 0, hi = 0;
        char c;
        List<Integer> res = new ArrayList<>();
        while (hi < len) {
            c = chs[hi];
            if (map[c - 'a'] > 0) {
                map[c - 'a']--;
                hi++;
                count--;
                if (count == 0) res.add(lo);
            } else {
                // 1. hi处字符不需要，“abc" "ab" chs[hi] = c是不需要的
                while (map[chs[hi] - 'a'] <= 0 && lo < hi) {
                    map[chs[lo] - 'a']++; //hi之前划过的都是需要的字符，因此count，map都需要复原
                    lo++;
                    count++;
                }

                if (lo == hi) {
                    //此时，lo与hi都来到了c的位置
                    if (map[chs[lo] - 'a'] <= 0) { //c为不需要的字符，lo与hi都移动到他的右边，重新进行遍历
                        lo++;
                        hi++;
                    }
                }
            }
        }
        return res;
    }
    }

    @Test
    public void test() {
        String s = "cbaebabacd", p = "abc";
        Solution1 so = new Solution1();
        Solution s1 = new Solution();
        System.out.println(so.findAnagrams(s, p));
        System.out.println(s1.findAnagrams(s, p));

    }
    @Test
    public void testE() {
        Map<String, Integer> map = new HashMap<>();
        map.put("1", 1);
        Map<String, Integer> map2 = new HashMap<>();
        map2.put("2", 2);
        // map.clear();
        map.putAll(map2);
        System.out.println(map);
    }
}
